// 线性表的合并


// 1.有序表合并——用顺序表实现
void Mergelist_Sq(SqList LA, SqList LB, SqList &LC)
{
    pa = LA.elem; // elem是动态数组指针，指向数组首元素地址（见下）
    pb = LB.elem;

    LC.length = LA.length + LB.length;                          // 合并后的链表长度
    LC.elem = (ElemType *)malloc(LC.length * sizeof(ElemType)); // 创建新的动态数组指针LC.elem
    pc = LC.elem;                                               // 指针，指向 LC.elem，用于插入元素

    pa_last = LA.elem + LA.length - 1; // 指向LA的最后一个元素，便于在合并时进行比较
    pa_last = LB.elem + LB.length - 1; // 就是首元素地址再加上其余元素后的位置

    while (pa <= pa_last && pb <= pb_last)
    { // 当指针没到头时
        if (*pa <= *pb)
            *pc++ = *pa++; // 取值比较，将值小的赋给数组c，并移动指针
        else
            *pc++ = *pb++;
    }

    while (pa <= pa_last)
        *pc++ = *pa++; // LB表已到达表尾，将LA中剩余的元素加入到LC
    while (pb <= pb_last)
        *pc++ = *pb++; // 同理
}

typedef int ElemType; // 定义ElemType为int，顺序表可以存储int类型的元素
struct SqList
{
    ElemType *elem; // elem可以看作指向动态数组的指针
    int length;     // 当前元素的个数
};




// 2.有序表合并——用链表实现
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{
    pa = La->next;
    pb = Lb->next;   // 指向首元节点
    pc = Lc = La;    // 用La的头节点作为Lc的头节点
    while (pa && pb) // 当指针域不为空时
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next; // 往Lc添加节点a，并更新pc和pa
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pa = pb->next;
        }
    }

    pc->next = pa ? pa : pb; // 插入剩余段
    free(Lb);
}